package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

/**
 * @Author: tgy
 * @Date: 1/30/21 2:05 PM
 */
public class _04_二叉树的序列化与反序列化_levelorder {


    /**
     * #:表示节点为空，
     * !:节点结束
     * @param root
     * @return
     */
    public static String serialize(TreeNode root) {

        if (root == null) {

            return "";
        }

        StringBuilder sb = new StringBuilder();

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();

            if (node == null) {

                sb.append("#!");
                continue;
            }else {

                sb.append(node.val).append("!");
            }

            queue.offer(node.left);
            queue.offer(node.right);
        }

        return sb.toString();
    }



    public static TreeNode deserialize(String serialize) {

        if (serialize == null || serialize.length() == 0) {

            return null;
        }

        String[] vals = serialize.split("!");

        List<String> valList = Arrays.stream(vals).collect(Collectors.toList());

        String rootVal = valList.remove(0);

        TreeNode root = new TreeNode(Integer.parseInt(rootVal));

        Queue<TreeNode> queue = new LinkedList<>();
        /**
         * 放入queue的是为了在下面拿出来，赋值left，right
         */
        queue.offer(root);

        while (!queue.isEmpty() && valList.size() > 0) {

            TreeNode node = queue.poll();
            String leftValStr = valList.remove(0);

            if (!leftValStr.equals("#")) {

                node.left = new TreeNode(Integer.parseInt(leftValStr));
                queue.offer(node.left);
            }

            String rightValStr = valList.remove(0);

            if (!rightValStr.equals("#")) {

                node.right = new TreeNode(Integer.parseInt(rightValStr));
                queue.offer(node.right);
            }
        }

        return root;
    }


    public static void main(String[] args) {
        /**
        *
        *          3
        *        /  \
        *       1    5
        *       \   / \
        *       2  4  6
        *      / \  \
        *    -10 -20 8
        */
        TreeNode root = new  TreeNode(3);

        root.left = new TreeNode(1);
        root.right = new TreeNode(5);
        //        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(-10);
        root.left.right.right = new TreeNode(-20);
        //        root.left.right.right.right = new TreeNode(-30);
        //        root.left.right.right.right.left = new TreeNode(-40);

        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(6);
        root.right.left.right = new TreeNode(8);

        System.out.println(serialize(root));

//        String[] split = "3!1!#!2!-10!#!#!-20!#!#!5!4!#!8!#!#!6!#!#!".split("!");
//        TreeNode rootNode = deserialize("3!1!#!2!-10!#!#!-20!#!#!5!4!#!8!#!#!6!#!#!");

        TreeNode rootNode = deserialize(serialize(root));
        System.out.println(rootNode);
    }
}
